#include <iostream>
#include <vector>
#include <stack>
#include <utility>
#include <random>
#include <chrono>

using namespace std;

class Timer
{
public:
    Timer() : beg_(clock_::now()) {}
    void reset() { beg_ = clock_::now(); }
    double elapsed() const { 
        return std::chrono::duration_cast<second_>
            (clock_::now() - beg_).count(); }

private:
    typedef std::chrono::high_resolution_clock clock_;
    typedef std::chrono::duration<double, std::ratio<1> > second_;
    std::chrono::time_point<clock_> beg_;
};

int LeftChild(int idx) {
    return (idx << 1) + 1;
}

void PercolateDown(vector<int> &arr, int idx, int size) {
    int child = LeftChild(idx), val;
    while (child < size) {
        if ((child + 1) < size && arr[child] < arr[child+1]) {
            child += 1;
        }
        if (arr[idx] < arr[child]) {
            val = arr[idx];
            arr[idx] = arr[child];
            idx = child;
            arr[idx] = val;
            child = LeftChild(idx);
        } else break;  // should not go down if all the child less than current value!
    }
}

// Sorting using a max-heap to sort array
void HeapSort(vector<int> &arr) {
    int n = arr.size();
    int i;
    for (i = (n >> 1); i >= 0; --i){
        PercolateDown(arr, i, arr.size());
    }
    int tmp;
    for (i = n - 1; i > 0; --i) {
        tmp = arr[i];
        arr[i] = arr[0];
        arr[0] = tmp;
        PercolateDown(arr, 0, i);
    }
}

void InsertionSort(vector<int> &arr) {
    int i, j, val, n = arr.size() - 1;
    for (i = 0; i < n; ++i) {
        val = arr[i + 1];
        for (j = i + 1; j > 0; --j) {
            if (arr[j-1] >= val) arr[j] = arr[j-1];
            else break;
        }
        arr[j] = val;
    }
}

void Merge(vector<int> &arr, vector<int> &tmp_arr, int lo, int hi) {
    if ((hi - lo) <= 1) {
        tmp_arr[lo] = arr[lo];
        return;
    }
    if ((hi - lo) == 2) {
        if (arr[lo] > arr[hi-1]) {
            int tmp = arr[lo];
            arr[lo] = arr[hi-1];
            arr[hi-1] = tmp;
        }
        tmp_arr[lo] = arr[lo];
        tmp_arr[hi-1] = arr[hi-1];
        return;
    }
    int mid = lo + ((hi - lo) >> 1);
    Merge(arr, tmp_arr, lo, mid);
    Merge(arr, tmp_arr, mid, hi);
    int i = lo, j = mid, p = lo;
    while (i < mid && j < hi) {
        if (arr[i] < arr[j]) {
            tmp_arr[p++] = arr[i++];
        } else {
            tmp_arr[p++] = arr[j++];
        }
    }
    while (i < mid) {
        tmp_arr[p++] = arr[i++];
    }
    while (j < hi) {
        tmp_arr[p++] = arr[j++];
    }
    for (i = lo; i < hi; ++i) {
        arr[i] = tmp_arr[i];
    }
}

void MergeSort(vector<int> &arr) {
    if (arr.size() < 2) return;
    vector<int> tmp_arr(arr.begin(), arr.end());
    Merge(arr, tmp_arr, 0, arr.size());
}

inline void swap(vector<int> &arr, int ai, int bi) {
    int tmp = arr[ai];
    arr[ai] = arr[bi];
    arr[bi] = tmp;
}

void QuickSort(vector<int> &arr) {
    if (arr.size() > 1) {
        int n = arr.size() - 1;
        stack<pair<int, int>> s;
        s.push(make_pair(0, n));
        int lo, hi, mid, l, r;
        while (!s.empty()){
            lo = s.top().first;
            hi = s.top().second;
            s.pop();
            mid = lo + ((hi - lo) >> 1);
            if (lo < mid && arr[lo] > arr[mid]) swap(arr, lo, mid);
            if (lo < hi && arr[lo] > arr[hi]) swap(arr, lo, hi);
            if (mid < hi && arr[mid] > arr[hi]) swap(arr, mid, hi);
            l = lo;
            r = hi;
            do {
                while (l < mid && arr[l] < arr[mid]) ++l;
                while (mid < r && arr[r] > arr[mid]) --r;
                if (l < r) {
                    swap(arr, l, r);
                    if (l == mid) {
                        mid = r;
                        ++l;
                    }
                    else if (r == mid) {
                        mid = l;
                        --r;
                    } else {
                        ++l;
                        --r;
                    }
                } else {
                    ++l;
                    --r;
                    break;
                }
            } while (l <= r);
            if ((r - lo) < 1) {
                if ((hi - l) < 1) continue;
                s.push(make_pair(l, hi));
            } else if ((hi - l) < 1) {
                s.push(make_pair(lo, r));
            } else {
                s.push(make_pair(l, hi));
                s.push(make_pair(lo, r));
            }
        }
    }
}

static const int arr_size = 30000;

int main()
{
    mt19937 rng;
    rng.seed(random_device()());
    uniform_int_distribution<mt19937::result_type> dist100(1, 20000);
    vector<int> arr1;
    for (int i = 0; i < arr_size; ++i) {
        arr1.push_back(dist100(rng));
    }
    vector<int> arr2(arr1.begin(), arr1.end()), arr3(arr1.begin(), arr1.end()), arr4(arr1.begin(), arr1.end());
    Timer timer;
    double cost;
    timer.reset();
    InsertionSort(arr1);
    cost = timer.elapsed();
    for (int i = 0; i < arr_size; ++i) {
        for (int j = i + 1; j < arr_size; ++j) {
            if (arr1[j] < arr1[i]) {
                cout << "InsertionSort Failed!" << endl;
                goto HS;
            }
        }
    }
    cout << "InsertionSort Success: " << cost << endl;
HS:
    timer.reset();
    HeapSort(arr2);
    cost = timer.elapsed();
    for (int i = 0; i < arr_size; ++i) {
        for (int j = i + 1; j < arr_size; ++j) {
            if (arr2[j] < arr2[i]) {
                cout << "HeapSort Failed!" << endl;
                for (int a:arr2) cout << a << ",";
                cout << endl;
                goto MS;
            }
        }
    }
    cout << "HeapSort Success: " << cost << endl;
MS:
    timer.reset();
    MergeSort(arr3);
    cost = timer.elapsed();
    for (int i = 0; i < arr_size; ++i) {
        for (int j = i + 1; j < arr_size; ++j) {
            if (arr3[j] < arr3[i]) {
                cout << "MergeSort Failed!" << endl;
                for (int a:arr3) cout << a << ",";
                cout << endl;
                goto QS;
            }
        }
    }
    cout << "MergeSort Success: " << cost << endl;
QS:
    timer.reset();
    QuickSort(arr4);
    cost = timer.elapsed();
    for (int i = 0; i < arr_size; ++i){
        for (int j = i + 1; j < arr_size; ++j) {
            if (arr4[j] < arr4[i]) {
                cout << "QuickSort Failed!" << endl;
                for (int a:arr4) cout << a << ",";
                cout << endl;
                return -1;
            }
        }
    }
    cout << "QuickSort Success: " << cost << endl;
    return 0;
}

